DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.38

Boolean Function Analysis on High-Dimensional Expanders

Authors: Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders. Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing |X(k)|=O(n) points in comparison to binom{n}{k+1} points in the (k+1)-slice (which consists of all n-bit strings with exactly k+1 ones).

Cite as

Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. Boolean Function Analysis on High-Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dikstein_et_al:LIPIcs.APPROX-RANDOM.2018.38,
  author =	{Dikstein, Yotam and Dinur, Irit and Filmus, Yuval and Harsha, Prahladh},
  title =	{{Boolean Function Analysis on High-Dimensional Expanders}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.38},
  URN =		{urn:nbn:de:0030-drops-94421},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.38},
  annote =	{Keywords: high dimensional expanders, Boolean function analysis, sparse model}
}

Search Results

Documents authored by Dikstein, Yotam

Boolean Function Analysis on High-Dimensional Expanders

Abstract

Cite as

Thanks for your feedback!

Could not send message